In network modeling of complex systems one is often required to sample randomrealizations of networks that obey a given set of constraints, usually in formof graph measures. A much studied class of problems targets uniform sampling ofsimple graphs with given degree sequence or also with given degree correlationsexpressed in the form of a joint degree matrix. One approach is to use Markovchains based on edge switches (swaps) that preserve the constraints, areirreducible (ergodic) and fast mixing. In 1999, Kannan, Tetali and Vempala(KTV) proposed a simple swap Markov chain for sampling graphs with given degreesequence and conjectured that it mixes rapidly (in poly-time) for arbitrarydegree sequences. While the conjecture is still open, it was proven for specialdegree sequences, in particular, for those of undirected and directed regularsimple graphs, of half-regular bipartite graphs, and of graphs with certainbounded maximum degrees. Here we prove the fast mixing KTV conjecture fornovel, exponentially large classes of irregular degree sequences. Our method isbased on a canonical decomposition of degree sequences into split graph degreesequences, a structural theorem for the space of graph realizations and on afactorization theorem for Markov chains. After introducing bipartite splitteddegree sequences, we also generalize the canonical split graph decompositionfor bipartite and directed graphs.
展开▼
